import java.util.Arrays;

public class BinarySearchPractise {
    public int hIndex(int[] citations) {
        int sz = citations.length;
        int l = 0;
        int r = sz - 1;
        while(l <= r){
            int m = l + (r - l) / 2;
            if(citations[m] >= (sz-1-m+1)){
                r = m - 1;
            }else{
                l = m + 1;
            }
        }
        return l == sz ? 0 : Math.min(sz-1-l+1, citations[l]);
    }

    public int smallestDivisor(int[] nums, int threshold) {
        int l = 1;
        int r = 1000000;
        while(l <= r){
            int m = l + (r - l) / 2;
            long sum = 0;
            for(int e : nums){
                sum += (e%m)==0 ? e/m : e/m + 1;
            }
            if(sum <= threshold){
                r = m - 1;
            }else{
                l = m + 1;
            }
        }
        return l;
    }

    private long getSum(int[] time, long m){
        long ret = 0;
        for(int e : time){
            ret += m / e;
        }
        return ret;
    }

    public long minimumTime(int[] time, int totalTrips) {
        long l = 1;
        long r = (long)time[0] * totalTrips;
        while(l <= r){
            long m = l + ((r - l) >> 1);
            long tmp = getSum(time, m);
            if(tmp < totalTrips){
                l = m + 1;
            }else{
                r = m - 1;
            }
        }
        return l;
    }
}
